/*
 * shlist.h
 *
 *  Created on: Mar 19, 2010
 *      Author: jgrande
 */

#ifndef _SHLIST_H_
#define _SHLIST_H_

#include <assert.h>

#include "shptr.h"
#include "sem.h"
#include "../IO/log.h"

template <typename T, int M>
class SharedList {

public:

private:

	struct NodoLista {
		T elem;
		NodoLista* sig;
		int pos;
	};

	SharedPointer<NodoLista, M> nodos;
	SharedPointer<bool, M> libres;
	SharedPointer<NodoLista*> primero, ultimo;
	Semaphore mutex;
	bool creado;

	int buscarLibre() {
		for(int i=0;i<M;i++) {
			if(libres[i]) return i;
		}

		return -1;
	}

	SharedList(const SharedList&);
	SharedList& operator=(const SharedList&);

public:

	class Iterador {

		NodoLista* actual;

	public:

		Iterador():actual(NULL) {}
		Iterador(NodoLista* nodo):actual(nodo) {}
		~Iterador() {}

		bool hasNext() const {
			return actual!=NULL;
		}

		T next() {
			T result = actual->elem;
			actual = actual->sig;
			return result;
		}
	};

	SharedList():
		creado(false) {
		nodos.allocate();
		libres.allocate();
		primero.allocate();
		ultimo.allocate();
		mutex.init(1);

		if(!nodos || !libres || !primero || !ultimo || !mutex) {
			if(nodos) nodos.free();
			if(libres) libres.free();
			if(primero) primero.free();
			if(ultimo) ultimo.free();
			if(mutex) mutex.destroy();
			return;
		} else {
			for(int i=0;i<M;i++) {
				libres[i] = true;
			}
		}

		this->creado = true;
	}

	~SharedList() {
		if(nodos) nodos.free();
		if(libres) libres.free();
		if(primero) primero.free();
		if(ultimo) ultimo.free();
		if(mutex) mutex.destroy();
	}

	void lock() {
		mutex.wait();
	}

	void unlock() {
		mutex.signal();
	}

	bool add(T elem) {
		int i = buscarLibre();

		if(i==-1) {
			return false;
		}

		NodoLista* nodo = (NodoLista*)nodos+i;
		libres[i] = false;

		nodo->elem = elem;
		nodo->sig = NULL;
		nodo->pos = i;

		if(*primero==NULL) { // lista vacía
			*primero = nodo;
		} else {
			(*ultimo)->sig = nodo;
		}

		*ultimo = nodo;

		return true;
	}

	bool remove(T elem) {
		NodoLista* nodo = *primero;
		NodoLista* anterior = NULL;

		while(nodo && nodo->elem!=elem) {
			anterior = nodo;
			nodo = nodo->sig;
		}

		if(nodo) {
			if(anterior==NULL) {
				*primero = nodo->sig;
			} else {
				anterior->sig = nodo->sig;
			}
			if(*ultimo==nodo) {
				*ultimo = anterior;
			}
			libres[nodo->pos] = true;
			return true;
		} else {
			return false;
		}

	}

	Iterador iterar() {
		return Iterador(*primero);
	}

	operator bool() const {
		return creado;
	}

};
/*
void shlistTest() {
	SharedList<int, 4> shlist;
	SharedList<int, 4>::Iterador it;

	assert(shlist);

	// inserta tres elementos y los itera

	assert(shlist.add(1));
	assert(shlist.add(2));
	assert(shlist.add(3));

	it = shlist.iterar();

	assert(it.hasNext());
	assert(it.next()==1);
	assert(it.hasNext());
	assert(it.next()==2);
	assert(it.hasNext());
	assert(it.next()==3);
	assert(!it.hasNext());

	// elimina un elemento inexistente

	assert(!shlist.remove(4));

	// elimina un elemento existente

	assert(shlist.remove(2));

	it = shlist.iterar();

	assert(it.hasNext());
	assert(it.next()==1);
	assert(it.hasNext());
	assert(it.next()==3);
	assert(!it.hasNext());

	// agrega dos nuevos elementos. uno debería ubicar el hueco que dejó
	// el 2 y el otro ocupar el hueco libre

	assert(shlist.add(4));
	assert(shlist.add(5));

	it = shlist.iterar();

	assert(it.hasNext());
	assert(it.next()==1);
	assert(it.hasNext());
	assert(it.next()==3);
	assert(it.hasNext());
	assert(it.next()==4);
	assert(it.hasNext());
	assert(it.next()==5);
	assert(!it.hasNext());

	// intenta agregar un elemento con la lista llena

	assert(!shlist.add(6));

	// elimina todos los elementos

	assert(shlist.remove(1));
	assert(shlist.remove(3));
	assert(shlist.remove(4));
	assert(shlist.remove(5));

	it = shlist.iterar();

	assert(!it.hasNext());

	// inserta un elemento nuevamente

	assert(shlist.add(1));

	it = shlist.iterar();

	assert(it.hasNext());
	assert(it.next()==1);
	assert(!it.hasNext());

	// elimina el único elemento

	assert(shlist.remove(1));

	it = shlist.iterar();

	assert(!it.hasNext());
}
*/
#endif /* _SHLIST_H_ */
